#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int KeyType;
typedef struct BSTNode {
    KeyType key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

//递归方式将元素插入二叉排序树中
int BST_Insert_Recursion(BSTree &tree, KeyType k) {
    if (tree == NULL) {
        tree = (BSTree) calloc(1, sizeof(BSTNode));
        tree->key = k;
        return 1;
    } else if (k == tree->key) {
        return 0;
    } else if (k > tree->key) {
        return BST_Insert_Recursion(tree->rchild, k);
    } else {
        return BST_Insert_Recursion(tree->lchild, k);
    }
}

void Create_BST(BSTree &tree, KeyType *str, int len) {
    int i;
    for (i = 0; i < len; i++) {
        BST_Insert_Recursion(tree, str[i]);
    }
}

int compare(const void *left, const void *right) {
    return *(int *) (left) - *(int *) (right);
}

//中序遍历
void InOrder(BSTree tree) {
    if (tree) {
        InOrder(tree->lchild);
        printf("%2d ", tree->key);
        InOrder(tree->rchild);
    }
}

//二叉查找树的删除操作
void Delete_element_BST(BSTree &tree, KeyType num) {
    if (tree == NULL) {
        return;
    }
    //如果当前结点大于要删除的结点，往左子树找
    if (tree->key > num) {
        Delete_element_BST(tree->lchild, num);
    } else if (tree->key < num) {
        //如果当前结点小于要删除的结点，往右子树找
        Delete_element_BST(tree->rchild, num);
    } else {
        //找到要删除的节点
        if (tree->lchild == NULL) {
            //如果左子树为空，则右子树直接顶上去
            BSTree temp = tree;//临时指针
            //用临时存着的目的是一会儿要free
            tree = tree->rchild;
            free(temp);
        } else if (tree->rchild == NULL) {
            //如果右子树为空，则左子树直接顶上去
            BSTree temp = tree;
            tree = tree->lchild;
            free(temp);
        } else {
            //左右孩子都不为空
            /*一般删除的策略：左子树的最大数据（左子树的最右结点）或右子树的最小数据（右子树的最左结点）
             * 代替要删除的结点(这里采用查找左子树的最大数据来代替，最大数据：左子树的最右结点)
             * */
            BSTree tempNode = tree->lchild;
            while (tempNode->rchild != NULL) {//向右边找到最大的
                tempNode = tempNode->rchild;
            }
            tree->key = tempNode->key;//把tempNode对应的值替换到要删除的值的位置上
            Delete_element_BST(tree->lchild, tempNode->key);//在左子树中找到tempNode的值，将其删除
        }
        return;
    }
}

//二叉排序树删除
int main() {

    BSTree tree = NULL;
    KeyType num;
    KeyType str[7];
    for (int &i:str) {
        i = rand() % 100;
    }
    for (int i:str) {
        printf("%2d ", i);
    }
    //C++自带的排序函数（数组名，数组长度，数组元素类型，compare函数）
//    qsort(str,7,sizeof(KeyType),compare);
    Create_BST(tree, str, 7);
    printf("\nDelete the queue before the element\n");
    //中序遍历
    InOrder(tree);
    //二叉查找树的删除操作
    printf("\nPlease enter the value you want to delete:\n");
    scanf("%d", &num);
    Delete_element_BST(tree, num);
    printf("The queue after the element is deleted:\n ");
    InOrder(tree);
    return 0;
}
